﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.IO;

namespace MergulhoGrafo
{
    public class GrafoRetangulo
    {
        #region Atributos

        private List<Retangulo> TodosRetangulos = new List<Retangulo>();
        private Hashtable TabelaRetangulos = new Hashtable();
        private int _NumeroFaces;
        public int numeroVertices;

        #endregion

        #region Propriedade

        public int NumeroFaces
        {
            get
            {
                return _NumeroFaces;
            }
        }

        #endregion

        #region Construtor

        public GrafoRetangulo(string arquivo)
        {
            TextReader txtEntradaProblema = new StreamReader(arquivo);
            
            numeroVertices = Convert.ToInt32(txtEntradaProblema.ReadLine());

            for (int i = 0; i < numeroVertices; i++)
            {
                string read = txtEntradaProblema.ReadLine();

                string[] linha = read.Split(' ');

                for (int j = 0; j < linha.Length; j++)
                {
                    int numeroRef = Convert.ToInt32(linha[j]);
                    this.CrieRetangulo(numeroRef, i+1);
                }

                // for para construir os links entre os retângulos construidos

                for (int j = 0; j < linha.Length; j++)
                {
                    if (j != linha.Length - 1)
                    {
                        int numeroRef = Convert.ToInt32(linha[j]);
                        Retangulo ret = (Retangulo)TabelaRetangulos["" + numeroRef];
                        int numeroRef2 = Convert.ToInt32(linha[j + 1]);
                        Retangulo ret2 = (Retangulo)TabelaRetangulos["" + numeroRef2];
                        this.ConectarEsqComDir(ret, ret2);
                    }
                    else
                    {
                        int numeroRef = Convert.ToInt32(linha[j]);
                        Retangulo ret = (Retangulo)TabelaRetangulos["" + numeroRef];
                        int numeroRef2 = Convert.ToInt32(linha[0]);
                        Retangulo ret2 = (Retangulo)TabelaRetangulos["" + numeroRef2];
                        this.ConectarEsqComDir(ret, ret2);
                    }
                }
            }

            int numTwirl = Convert.ToInt32(txtEntradaProblema.ReadLine());

            for (int i = 0; i < numTwirl; i++)
            {
                int index_vert = Convert.ToInt32(txtEntradaProblema.ReadLine());
                Retangulo ret2 = (Retangulo)TabelaRetangulos["" + index_vert];
                ret2.TocerAresta();
            }

            AtualizarFaces(TodosRetangulos);

            Console.WriteLine("Hello World");
            Console.WriteLine("Quantidade de Retângulos: " + TodosRetangulos.Count);
            //Console.ReadKey();

            txtEntradaProblema.Close();
        }

        #endregion

        #region Propriedades

        public List<Retangulo> Retangulos
        {
            get { return this.TodosRetangulos; }
        }

        #endregion

        #region Métodos

        private void ConectarEsqComDir(Retangulo ret, Retangulo ret2)
        {
            Nodo esq = ret.NodoEsqIni();
            Nodo dir = ret2.NodoDirIni();

            if (esq.NaoTemLink && dir.NaoTemLink)
            {
                esq.Link = dir;
            }
            else if (esq.NaoTemLink)
            {
                dir = ret2.NodoDirSup();

                if (dir.NaoTemLink)
                {
                    esq.Link = dir;
                }
                else
                {
                    throw new Exception("Erro na construção dos links");
                }
            }
            else if (dir.NaoTemLink)
            {
                esq = ret.NodoEsqSup();

                if (esq.NaoTemLink)
                {
                    esq.Link = dir;
                }
                else
                {
                    throw new Exception("Erro na construção dos links");
                }
            }
            else
            {
                esq = ret.NodoEsqSup();
                dir = ret2.NodoDirSup();

                if (esq.NaoTemLink && dir.NaoTemLink)
                {
                    esq.Link = dir;
                }
                else
                {
                    throw new Exception("Erro na construção dos links");
                }
            }
        }

        public void CrieRetangulo(int numeroRef, int numLinha)
        {
            if (NaoExistir(numeroRef))
            {
                Retangulo novoRetangulo = new Retangulo(numeroRef);
                novoRetangulo.Vert1 = numLinha;
                TodosRetangulos.Add(novoRetangulo);
                TabelaRetangulos.Add("" + numeroRef, novoRetangulo);
            }
            else
            {
                Retangulo retangulo = (Retangulo)TabelaRetangulos["" + numeroRef];
                retangulo.Vert2 = numLinha;
            }
        }

        public List<Retangulo> Dual()
        {
            List<Retangulo> newRetangles = new List<Retangulo>();

            foreach (Retangulo retangulo in TodosRetangulos)
            {
                Retangulo newRetangulo = retangulo.Dual();

                newRetangles.Add(newRetangulo);
            }

            int numeroFaces = AtualizarFaces(newRetangles);

            return newRetangles;
        }

        private int AtualizarFaces(List<Retangulo> newRetangles)
        {
            int indexFace = 1;
            Hashtable TabelaNodosVisitados = new Hashtable();

            while (TabelaNodosVisitados.Count != newRetangles.Count * 4)
            {
                Nodo nodoAtual = GetNodo(newRetangles, TabelaNodosVisitados);
                Nodo nodoInicial = nodoAtual;
                if (nodoAtual != null)
                {
                    do
                    {
                        if (Esquerda(nodoAtual))
                        {
                            nodoAtual.Pai.Face1 = indexFace;
                        }
                        else
                        {
                            nodoAtual.Pai.Face2 = indexFace;
                        }

                        TabelaNodosVisitados.Add("" + nodoAtual.GetNumeroRef(), nodoAtual);
                        TabelaNodosVisitados.Add("" + nodoAtual.Longo.GetNumeroRef(), nodoAtual.Longo);
                        nodoAtual = nodoAtual.Longo.Link;
                    }
                    while (nodoAtual.GetNumeroRef() != nodoInicial.GetNumeroRef());
                    indexFace++;
                }
                else
                {
                    throw new Exception("Erro na geração das faces");
                }
            }
            this._NumeroFaces = indexFace - 1;
            return indexFace;
        }

        private Nodo GetNodo(List<Retangulo> newRetangles, Hashtable TabelaNodosVisitados)
        {
            foreach (Retangulo ret in newRetangles)
            {
                if (!TabelaNodosVisitados.Contains("" + ret.NodoEsqIni().GetNumeroRef()))
                {
                    return ret.NodoEsqIni();
                }
                else if (!TabelaNodosVisitados.Contains("" + ret.NodoDirIni().GetNumeroRef()))
                {
                    return ret.NodoDirIni();
                }
            }

            return null;
        }

        private bool Esquerda(Nodo nodoAtual)
        {
            return nodoAtual.GetNumeroRef() == nodoAtual.Pai.NodoEsqIni().GetNumeroRef()
                || nodoAtual.GetNumeroRef() == nodoAtual.Pai.NodoDirSup().GetNumeroRef();
        }

        private bool NaoExistir(int numeroRef)
        {
            object temp = TabelaRetangulos["" + numeroRef];
            
            if(temp == null)
            {
                return true;
            }

            return false;
        }
        
        internal void ContrairGrafo(List<int> arvoreGeradora)
        {
            List<Retangulo> grafo2 = new List<Retangulo>();
            grafo2.AddRange(this.TodosRetangulos);

            foreach (int aresta in arvoreGeradora)
            {
                Retangulo retParaContrair = null;
                foreach (Retangulo ret in grafo2)
                {
                    if (ret.numeroRef == aresta)
                    {
                        retParaContrair = ret;
                        break;
                    }
                }
                retParaContrair.Contrair();
            }
        }
        #endregion
    }
}
